Many parallel systems that have multiple processor units and multiple tasks to perform have a problem of distribution of the tasks between the processors. In common cases, a full search is made through all possible combinations of the tasks to find an optimal solution. Such full searches have exponential complexity and thus are not applicable where the tasks are not fixed, but are generated in a stream and should be scheduled on-the-fly.
Properties of the distribution among the processors sometimes make finding an optimal or nearly-optimal solution with non-exponential complexity possible. Some single tasks can be performed on multiple processor units but not in an arbitrary way. For example, memory sharing restricts how the tasks are performed. Another restriction is parallelizing overhead. When such restrictions appear, formalizing and encoding the rules of scheduling is difficult.
It would be desirable to implement a two-pass linear complexity task scheduler to accommodate on-the-fly scheduling for streams of tasks.